//hashCode函数
function hashFunc(str, max) {
    //1.定义hashCode
    let hashCode = 0;

    //3.霍纳算法
    for (let i = 0; i < str.length; i++) {
        hashCode = 31 * hashCode + str.charCodeAt(i)     //charCodeAt()获取acs码
    }

    hashCode = hashCode % max;//取余操作 获得

    return hashCode;
}

// 判断是否是质数 算法性能比较低
function isPrime(num) {
    for(let i = 2; i < num; i++) {
        if(num % i === 0) {
            return false;
        } 
    }
    return true;
}

//判断是否为质数，高质量人类算法
function isPrime(num) {
    let temp = Math.ceil(Math.sqrt(num));
    for (let i = 2; i <= temp; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}



const MAX_LOAD_FACTOR = 0.75;
const MIN_LOAD_FACTOR = 0.25;
export class HashTable {
    constructor() {
        this.storage = [];//数组长度
        this.count = 0;//当前存放了多少个元素
        this.limit = 8;//数组的最大长度
    }

    hashFunc(str, max) {
        let hashCode = 0;
        for (let i = 0; i < str.length; i++) {
            hashCode = 31 * hashCode + str[i].charCodeAt();
        }
        hashCode = hashCode % max;
        return hashCode;
    }
    //插入操作  HashMap => 键值对 {key: value}
    put(key, value) {
        const index = this.hashFunc(key, this.limit);//获取下标
        let bucket = this.storage[index];   //将获取到的hash表下标赋予给一个bucket数组 有时候存在this.storage[index] 越界为空值
        if (bucket == undefined) {//如果桶数组为空值，则把空数组赋予给bucket
            bucket = [];
            this.storage[index] = bucket;
        }
        let overide = false;//创建overide 用于判断是否
        for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] === key) {
                tuple[1] = value;
                overide = true;
            }
        }
        if (!overide) {
            bucket.push([key, value]);
            this.count++;
            if (this.count > this.limit * MAX_LOAD_FACTOR) {
                let newLimit = this.limit * 2;
                this.resize(this.getPrime(newLimit));
            }
        }
    }

    //根据key值查找value
    get(key) {
        const index = this.hashFunc(key, this.limit);
        let bucket = this.storage[index];
        if (bucket !== undefined) {
            for (let i = 0; i < bucket.length; i++) {
                let tuple = bucket[i];
                if (tuple[0] === key) {
                    return tuple[1];
                }
            }
        } else return null;
    }

    //remove删除hash中的某个元素
    remove(key) {
        const index = this.hashFunc(key, this.limit);
        let bucket = this.storage[index];
        if (bucket !== undefined) {
            for (let i = 0; i < bucket.length; i++) {
                let tuple = bucket[i];
                if (tuple[0] === key) {
                    bucket.splice(i, 1);
                    this.count--;
                    if (this.limit > 8 && this.count < this.limit * MIN_LOAD_FACTOR) {
                        let newLimit = Math.floor(this.limit / 2);
                        this.resize(this.getPrime(newLimit));
                    }
                }
            }
        } else return null;
    }
    //isEmpty()判断表是否为空
    isEmpty() {
        return this.count === 0;
    }
    //size() 返回hash长度
    size() {
        return this.count;
    }
    // resize()扩容
    resize(newLimit) {
        //1.把旧的表存储起来
        let oldStorage = this.storage;
        //2.重新表属性赋值
        this.limit = newLimit;
        this.count = 0;
        this.storage = [];
        //给表进行重新赋值
        oldStorage.forEach((bucket) => {
            if (bucket === undefined) {
                return
            }
            for (let i = 0; i < bucket.length; i++) {
                let tuple = bucket[i];
                this.put(tuple[0], tuple[1])
            }
        })
    }
    //判断是否是质数
    isPrime(num) {
        //1.向上去整取平方根
        let temp = Math.ceil(Math.sqrt(num));
        //2.进行判断书否为质数
        for (let i = 2; i < temp; i++) {
            if (num % i === 0) {
                return false;
            }
        }
        return true;
    }
    //根据是否是质数累加看是否是
    getPrime(num) {
        //循环判断是否是质数
        while(!this.isPrime(num)) {
            num++;
        }
        return num;
    }
}

const hashTable = new HashTable();
hashTable.put("name", "leilei");
// hashTable.put("name1", "leilei");
// hashTable.put("name", "leilei");

console.log(hashTable);
console.log(hashTable.get("name"));
